Chào mừng đến với Bài học 3 của Các Khái niệm Trí tuệ Nhân tạo (PolyU COMP5511). Trong buổi học này, chúng ta chuyển từ tìm đường cho tác nhân đơn lẻ sang Tìm kiếm Đối kháng, nơi các tác nhân hoạt động trong môi trường đa tác nhân cạnh tranh. Chúng ta cũng giới thiệu Bài toán Thỏa mãn Ràng buộc (CSPs), một mô hình mà mục tiêu là tìm một trạng thái thỏa mãn một tập hợp các ràng buộc cụ thể thay vì một đường đi.
Các Khái niệm Cốt lõi
- Tìm kiếm Đối kháng: Tập trung vào các thuật toán như Minimax và Cắt Alpha-Beta để đưa ra các quyết định hợp lý đối đầu với một đối thủ thông minh.
- Tìm kiếm Cây Monte Carlo (MCTS): Khám phá việc ra quyết định dựa trên xác suất, đóng vai trò là nền tảng cho các AI chơi game hiện đại như AlphaGo.
- Thỏa mãn Ràng buộc: Mô hình hóa các bài toán bằng Biến, Miền và Ràng buộc, được giải quyết thông qua Quay lui và Tìm kiếm cục bộ.
Phân tích Độ phức tạp
Trong các cài đặt đối kháng, độ phức tạp của không gian tìm kiếm thường được xác định bởi hệ số nhánh của trò chơi
Cảnh báo về sự thay đổi mô hình
Không giống như tìm kiếm tiêu chuẩn (ví dụ: A* hoặc BFS) nơi môi trường là tĩnh, Tìm kiếm Đối kháng giả định rằng môi trường (đối thủ) chủ động cố gắng giảm thiểu thành công của bạn. Trong CSPs, thứ tự hành động ít quan trọng hơn tính hợp lệ của việc gán cuối cùng.
Mã giả Khái niệm: Các Loại Tác nhân
1
# Tác nhân Đối kháng (Lý thuyết Trò chơi)
2
hàmDecide_Move( trạng thái):
3
trả vềMaximize_Utility( Predict_Opponent_Minimization( trạng thái))
4
5
# Bộ giải CSP (Logic Ràng buộc)
6
hàmSolve_CSP( biến, ràng buộc):
7
nếuAll_Constraints_Satisfied( phân công):
8
trả vềphân công
9
ngược lại:
10
trả vềBacktrack_Search( biến )
Lộ trình Khóa học
Chuyển từ Tìm kiếm (Bài học 2) sang Ra quyết định Chiến lược (Bài học 3).